| 翻訳と辞書 |
| configuration graph ： ウィキペディア英語版 |
configuration graph
Configuration graphs are a theoretical tool used in computational complexity theory to prove a relation between graph reachability and complexity classes.
== Definition ==
A theoretical computational model, like Turing machine or finite automata, explains how to do a computation. The model explains both what is an initial configuration of the machine and which steps can be taken to continue the computation, until we eventually stop. A ''configuration'', also called an ''Instantaneous Description(ID)'' is a finite representation of the machine at a given time. For example, for a finite automata and a given input, the configuration will be the current state and the number of read letters, for a Turing machine it will be the state, the content of the tape and the position of the head. A configuration graph is a directed labeled graph where the label of the vertices are the possible configurations of the models and where there is an edge from one configuration to another if it correspond to a computational step of the model.
The initial and accepting configuration(s) of the machine are special vertices of the configuration graph. The computation accepts if and only if there is a path from an initial vertex to an accepting vertex.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「configuration graph」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|